import java.util.Stack;

public class Sort {
    // 插入排序
    public static void insertSort(int[] array){
        for(int i = 1;i < array.length;i++){
            int j = i - 1;
            int tmp = array[i];
            for(;j >= 0;j--){
                if(array[j] > tmp){
                    array[j+1] = array[j];
                }else{
                    break;
                }
            }

            array[j + 1] = tmp;
        }
    }

    // 希尔排序
    public static void shellSort(int[] array){
        int gap = array.length;
        while(gap > 1){
            gap /= 2;
            shell(array,gap);
        }
    }

    // 对每组进行插入排序
    public static void shell(int[] array,int gap){
        for(int i = gap;i < array.length;i++){
            int j = i - gap;
            int tmp = array[i];
            for(;j >= 0;j -= gap){
                if(array[j] > tmp){
                    array[j+gap] = array[j];
                }else{
                    break;
                }
            }

            array[j + gap] = tmp;
        }
    }

    // 交换
    public static void swap(int i, int j, int[] array){
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

    // 选择排序
    public static void selectSort(int[] array){
        // 在i下标的后面找到比i下标对应的值的最小值,然后交换
        int n = array.length;
        for(int i = 0;i < n;i++){
            int minIndex = i;
            for(int j = i + 1;j < n;j++){
                if(array[j] < array[i]){
                   if(array[j] < array[minIndex]){
                       minIndex = j;
                   }
                }
            }
            swap(i,minIndex,array);
        }
    }

    public static void selectSort2(int[] array){
        // 在i下标的后面找到比i下标对应的值的最小值,然后交换
        int left = 0;
        int right = array.length - 1;
        while(left < right){
            int minIndex = left;
            int maxIndex = left;
            for(int i = left + 1;i <= right;i++){
                if(array[i] < array[minIndex]){
                    minIndex = i;
                }
                if(array[i] > array[maxIndex]){
                    maxIndex = i;
                }
            }
            swap(left,minIndex,array);
            // 第一个数是最大的数,防止最小的下标和第一个数换了,最大值就在minIndex的位置了
            if(maxIndex == left){
                maxIndex = minIndex;
            }
            swap(right,maxIndex,array);
            left++;
            right--;
        }
    }

    // 堆排序
    private static void shifDown(int[] array,int parent,int len){
        int child = 2 * parent + 1;
        while(child < len){
            if(child + 1 < len && array[child] < array[child + 1]){
                child++;
            }

            if(array[child] > array[parent]){
                swap(child,parent,array);
                parent = child;
                child = 2 * parent + 1;
            }else{
                break;
            }
        }
    }

    private static void createHeap(int[] array){
        // 建立大根堆
        for(int parent = (array.length - 1 - 1) / 2;parent >= 0;parent--) {
            shifDown(array, parent, array.length);
        }
    }

    public static void heapSort(int[] array){
        createHeap(array);
        int end = array.length - 1;
        while(end > 0){
            swap(end,0,array);
            shifDown(array,0,end);
            end--;
        }
    }

    // 冒泡排序
    public static void bubbleSort(int[] array){
        // i是趟数
        for(int i = 0;i < array.length;i++){
            // j是比较的大小的
            boolean flag = true;
            for(int j = 0;j < array.length - i - 1;j++){
                if(array[j] > array[j + 1]){
                    swap(j,j + 1,array);
                    flag = false;
                }
            }
            if(flag) {
                break;
            }
        }
    }


    // 快速排序
    public static void quickSort(int[] array){
        quick(array,0,array.length - 1);
    }

    // 三数取中法,求中位数的下标
    private static int middleNum(int[] array,int left,int right){
        int mid = (left + right) / 2;
        if(array[left] < array[right]){
            // 1. x < 3 < 9
            // 2. 3 < 9 < x
            // 3. 3 < x < 9
            if(array[mid] < array[left]){
                return left;
            }
            else if(array[mid] > array[right]){
                return right;
            }
            else{
                return mid;
            }
        }else{
            // 9 > 3 == left > right
            // 1. x > left > right
            if(array[mid] > array[left]){
                return left;
            }else if(array[right] > array[mid]){
                // 2. left > right > x
                return right;
            }else{
                // 3. left > x > right
                return mid;
            }
        }
    }

    public static void insertSort(int[] array,int left,int right){
        for(int i = left + 1;i <= right;i++){
            int j = i - 1;
            int tmp = array[i];
            for(;j >= left;j--){
                if(array[j] > tmp){
                    array[j+1] = array[j];
                }else{
                    break;
                }
            }

            array[j + 1] = tmp;
        }
    }

    private static void quick(int[] array,int start,int end){
        if(start >= end){
            return;
        }

        if(end - start + 1 <= 15){
            // 减少递归的次数
            // 因为最后几层节点数最多,递归次数也多
            insertSort(array,start,end);
            return;
        }

        // 1 2 3 4 5 6 7
        // 中间值的下标和第一个数交换,作为新的基准元素
        int index = middleNum(array,start,end);
        swap(index,start,array);
        // 4 2 3 1 5 6 7
        // 为了让左右分布更均匀,降低树的高度,减少递归的次数

        int prvot = partition(array,start,end);
        quick(array,start,prvot - 1);
        quick(array,prvot + 1,end);
    }

    // 霍尔法
    private static int partitionHoare(int[] array,int left,int right){
        // 基准元素
        int tmp = array[left];
        // 记录第一个基准下标
        int i = left;
        while(left < right) {
            // 必须先找先右再左
            // 找小
            while (left < right && array[right] >= tmp) {
                right--;
            }
            // 找大
            while (left < right && array[left] <= tmp) {
                left++;
            }
            swap(left, right, array);
        }
        swap(i,left,array);

        return left;
    }

    // 挖坑法
    private static int partitionHole(int[] array,int left,int right){
        // 基准元素
        int tmp = array[left];
        while(left < right) {
            // 必须先找先右再左
            // 找小
            while (left < right && array[right] >= tmp) {
                right--;
            }
            array[left] = array[right];
            // 找大
            while (left < right && array[left] <= tmp) {
                left++;
            }
            array[right] = array[left];
        }
        array[left] = tmp;

        return left;
    }

    // 前后指针法
    public static int partition(int[] array,int left,int right){
        int prev = left;
        int cur = left + 1;
        while(cur <= right){
            while(array[cur] < array[left] && array[++prev] != array[cur]){
                swap(cur,prev,array);
            }
            cur++;
        }
        swap(prev,left,array);

        return prev;
    }

    // 非递归实现快速排序
    public static void quickSortNor(int[] array){
        int start = 0;
        int end = array.length - 1;
        Stack<Integer> stack = new Stack<>();

        int pivot = partitionHoare(array,start,end);
        if(pivot - 1 > start){
            // 左边有两个元素
            stack.push(start);
            stack.push(pivot - 1);
        }
        else if(pivot + 1 < end){
            // 右边至少有两个元素
            stack.push(pivot + 1);
            stack.push(end);
        }
        // 找基准里面会互换元素进行排序
        while(!stack.empty()){
            end = stack.pop();
            start = stack.pop();

            pivot = partitionHoare(array,start,end);
            if(pivot - 1 > start){
                // 左边有两个元素
                stack.push(start);
                stack.push(pivot - 1);
            }
            else if(pivot + 1 < end){
                // 右边至少有两个元素
                stack.push(pivot + 1);
                stack.push(end);
            }
        }
    }

    // 归并排序
    public static void mergeSort(int[] array){
        merge(array,0,array.length - 1);
    }

    private static void merge(int[] array,int start,int end){
        if(start >= end){
            return;
        }

        int mid = (start + end) / 2;
        // 分解
        merge(array,start,mid);
        merge(array,mid + 1,end);
        // 合并
        mergeHeB(array,start,mid,end);
    }

    private static void mergeHeB(int[] array, int left, int mid, int right) {
        int s1 = left;
        int e1 = mid;
        int s2 = mid + 1;
        int e2 = right;

        // 新数组的下标
        int k = 0;
        int[] tmpArray = new int[right - left + 1];

        while(s1 <= e1 && s2 <= e2){
            if(array[s1] < array[s2]){
                tmpArray[k++] = array[s1++];
            }else{
                tmpArray[k++] = array[s2++];
            }
        }

        while(s1 <= e1){
            tmpArray[k++] = array[s1++];
        }

        while(s2 <= e2){
            tmpArray[k++] = array[s2++];
        }

        // left是因为有左边还有右边的数组
        // tmpArray是临时数组,会销毁的,需要拷贝回原来的数组
        for(int i = 0;i < tmpArray.length;i++){
            array[i + left] = tmpArray[i];
        }
    }

    // 非递归实现归并排序
    public static void mergeSortNor(int[] array){
        // gap表示每组的数据个数
        int gap = 1;
        while(gap < array.length){

            for(int i = 0;i < array.length;i = i + 2 * gap){
                int left = i;

                // mid和right可能会越界
                // 比如只有5个元素
                // 分解右边一半的时候
                // l = i mid = 5 r = 7
                int mid = left + gap - 1;
                int right = mid + gap;

                if(mid >= array.length){
                    mid = array.length - 1;
                }
                if(right >= array.length){
                    right = array.length - 1;
                }


                mergeHeB(array,left,mid,right);
            }

            gap *= 2;
        }
    }

    // 计数排序,指定范围内的数据进行排序
    public static void countSort(int[] array){
        int minVal = array[0];
        int maxVal = array[0];

        for(int i = 0;i < array.length;i++){
            if(minVal > array[i]){
                minVal = array[i];
            }
            if(maxVal < array[i]){
                maxVal = array[i];
            }
        }

        int len = maxVal - minVal + 1;
        int[] count = new int[len];
        for(int i = 0;i < array.length;i++){
            count[array[i] - minVal]++;
        }

        // 写回array数组中
        int k = 0;
        for(int i = 0;i < count.length;i++){
            while(count[i] > 0){
                array[k++] = i + minVal;
                count[i]--;
            }
        }
    }
}


/*
class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size(),n = matrix[0].size();
        vector<int> a(m);
        vector<int> b(n);
        for(int i = 0;i < m;i++){
            for(int j = 0;j < n;j++){
                if(matrix[i][j] == 0){
                  a[i] = 1;
                  b[j] = 1;
                }
            }
        }

        for(int i = 0;i < m;i++){
            for(int j = 0;j < n;j++){
                if(a[i] == 1 || b[j] == 1){
                    matrix[i][j] = 0;
                }
            }
        }
    }
};
 */
